package cn.zhl.algorithm._2_动态规划;

/**
 * @program: demos
 * @description: 最长上升子序列，严格上升，比如 [10,2,2,5,1,7,101,18]有两个，2,5,7,101;2,5,7,18
 * @author: 刘振华
 * @create: 2020-09-22 15:33
 **/
public class LongestLengthOfSubsequence {
	public static void main(String[] args) {
		int[] ints = {10,2,2,5,1,7,101,18};
		System.out.println(getLength(ints));
	}
	static int getLength(int[] nums){
		int len = nums.length;
		if(len<1){
			return -1;
		}
		int[] dp = new int[len];
		dp[0] = 1;
		int max = 0;
		System.out.print(dp[0]+"\t");
		for(int i = 1; i < len ; i++){
			int tmpMax = 0;
			for(int j = 0 ; j < i ; j++){
				int target = nums[j];
				if(nums[i] > target && tmpMax < target){
					tmpMax = dp[j];
				}
			}
			dp[i] = tmpMax + 1;
			if(max <= dp[i]){
				max = dp[i];
			}
		}
		return max;
	}
}
